NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/5713

Internet Message Format | 1996-08-05 | 3.3 KB

Path: news.cs.tut.fi!usenet
From: [e-mail] (Tero Pulkkinen)
Newsgroups: comp.lang.c,rec.games.programmer
Subject: Re: Speed question here...
Date: 20 Feb 1996 14:42:26 +0200
Organization: Tampere University of Technology, Finland
Sender: [e-mail]
Distribution: inet
Message-ID: <[e-mail]>
References: <4ftluh$[e-mail]> <4g9rbg$[e-mail]>
NNTP-Posting-Host: korppi.cs.tut.fi
NNTP-Posting-User: p150650
In-reply-to: [e-mail]'s message of Mon, 19 Feb 1996 20:10:06 GMT
X-Newsreader: Gnus v5.0.15

   >I was curious as to how fast something like the
   >following would execute:

   >    int x;
   >    node *ptr;   ptr in linked list

   >       for ( ptr = first_node; ptr != NULL; ptr = ptr.next ) {
   >       for ( x = 0; x < max; x++ ) {
   >        array[x] = array_other[x];
   >           }
   >      }

   >I really am not interested in the assignment statement, that's easy.
   >but the traversal through the linked list, and inner integer incremental
   >for loop for each node visited.  How fast is a traversal through
   >a linked list when you do a for loop at each node?

You should be interested in the assignment, coz its the slowest part of that
code. :) If the array item happens to be something else than sizeof 2^n then
that assignment requires at least one multiply. :) Slow as hell. better
do it this way:

for(arrayptr=array, array_otherptr=array_other, ptrend=arrayptr+max;
    arrayptr<ptrend;) {
    *arrayptr++=*array_otherptr++;
}

That way it only does the multiplication (if it requires that) outside
the loop instead of doing it every iteration. Usually that index-presentation
is not too good, and the only posible place for multiplication in that one
can be reduced out to use pointers at the first place instead of arbitrary
index that has nothing to do with the data we really want to represent.
(and here we really want to represent positions in an array, not some
dummy integer values... :)

Indexing with constant value is ok with efficency, but if you need to put
a variable to it, then you'd really consider if it can be done any other
way.

And btw, if you want fast code, you should use do { } while() -construct
instead of for(;;) -loop. That way you avoid having two jumps inside the
loop. And if you have situation where you always dont have to execute the
insides of the loop, then can do it with an if... Most compilers put the
loop test to the start of the loop block, and then do unconditional jump
to the start of it. That's one too much. :)

Propably the best way of doing the situation you had is like this:

array_type *p1=array,*p2=array_other,*pend=array_end;
node *ptr;   //ptr in linked list

if (ptr)
do {
  do {
    *p1++=*p2++;
  } while (p1<pend);
  ptr=ptr->next; // note your code had a bug here, using pointer it must be ->
} while (ptr);

This code doesnt look nice, and these things should be only done at the last
possible optimization you'll make, but in some cases the result might be
like twice faster or something.

>  BTW: Both if this question has any sense or not (my opinion is that
>  hasn't)... is anyway graphic related ?

ok, removed this from comp.graphics.algorithms, its now only at somehow
proper groups...

-- Codex / Paranoids
-- Tero Pulkkinen -- [e-mail] --